public class SolutionInterview16_17 {
    public int maxSubArray(int[] nums) {
        int max=nums[0],ans=nums[0];
        for (int i=1;i<nums.length;i++) {
            max=Math.max(nums[i],max+nums[i]);
            ans=Math.max(ans,max);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview16_17().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
